package leetcode_core.leetcode_6;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月19日 20:46
 */
public class LongestPalindrome2 {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n == 0){
            return "";
        }
        //1. 状态:当前检查得到的子串,子串的状态可以由左右边界确定,也就是[l,r]
        //2.1 选择:检查s[l-1]和s[r+1]是否相同,如果相同,那么子串扩大为[l-1,r+1],同时标记
        //2.2 定义dp数组
        char[] str = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        //3.1 base-case:当l == r的时候,dp[l][r] = true
        for(int i = 0;i<n;i++){
            dp[i][i] = true;
        }
        //3.2 状态转移方程,枚举所有的[i...j],i∈[0,n],j∈[0,n]
        int[] max = new int[]{0,0,1};
        //状态转移方程的具体过程:
        //目前初始化的状态为[i,j](i==j)=true
        //那么要推导的就是从[i,j](s[i,j]上所有的子串都是否是回文字串)
        //1. 如果i == j,也就是说i-j+1 = 1=>i ==j的时候,此时是回文子串
        //此时是否是回文子串,取决于s[i] == s[j]?如果等于,那么也是回文子串
        for(int j =  1; j < n ;j++){
            for(int i = 0;i < j ;i++){
                if(str[i] != str[j]){
                    dp[i][j] = false;
                    continue;
                }
                if(j - i -1 <= 0 ){
                    //2. 如果i+1 == j,也就是说区间[i,j]包含两个元素,也就是j-i+1 = 2,化简得j-i-1 = 0
                    dp[i][j] = true;
                }else if(j - i - 2 >=0 && dp[i+1][j-1]){
                    //3. 如果[i,j]包含了三个元素,也就是j - i +1 >= 3,也就是j-i-2>=0
                    //此时如果dp[i+1,j-1]== true,而且s[i] == s[j],则dp[i,j] = true
                    //由于定义的区间是[i,j],而i严格小于j
                    dp[i][j] = true;
                }
                if(dp[i][j] && j-i+1 > max[2]){
                    max[0] = i;max[1] = j;max[2] = j-i+1;
                }
            }
        }
        return s.substring(max[0],max[1]+1);
    }

    @Test
    public void test(){
        System.out.println(longestPalindrome("aacabdkacaa"));
    }


}
